Package edu.claflin.finder.algo.clustering.struct

Class BinarySearchTree<T extends TreeNodeInfo>

java.lang.Object
edu.claflin.finder.algo.clustering.struct.BinarySearchTree<T>
public class BinarySearchTree<T extends TreeNodeInfo> extends Object

  • Field Details

    • root

      private TreeNode<T extends TreeNodeInfo> root

    • allow_duplicates

      private boolean allow_duplicates

  • Constructor Details

    • BinarySearchTree

      public BinarySearchTree()
      Create an empty BinarySearchTree.

    • BinarySearchTree

      public BinarySearchTree(boolean dup)

  • Method Details

    • allows_duplicates

      public boolean allows_duplicates()

    • isEmpty

      public boolean isEmpty()
      Is the BinarySearchTree empty?
      Returns:
      true if empty, false otherwise

    • clear

      public void clear()

    • add

      public void add(T info)
      Addd a new Tree Node with the given j index and q value
      Parameters:
      info - the key

    • add

      private void add(T info, TreeNode<T> p)
      Recursive implementation of add.
      Parameters:
      info - the key
      p - the current top Tree Node

    • getVal

      public Double getVal(T info)

    • get

      public T get(T info)

    • get

      private TreeNode<T> get(T info, TreeNode<T> p)

    • set

      public void set(T info)

    • contains

      public boolean contains(T info)
      Is the specified ElemntType in the BinarySearchTree?
      Parameters:
      info - the key
      Returns:
      true if it is contained, false otherwise

    • contains

      private boolean contains(T info, TreeNode<T> p)

    • toString

      public String toString()
      Gets an inorder String representation of the BinarySearchTree.
      Overrides:
      toString in class Object
      Returns:
      the BinarySearchTree as a String

    • toString

      private String toString(TreeNode<T> p)
      Recursive implementation of inorder toString.
      Parameters:
      p - the current TreeNode to print and recursive parameter
      Returns:
      the BinarySearchTree as a String

    • getMin

      public T getMin()

    • getMin

      private T getMin(TreeNode<T> p)

    • getMax

      public T getMax()

    • getMax

      public T getMax(TreeNode<T> p)

    • remove

      public void remove(T info)

    • remove

      private TreeNode<T> remove(T info, TreeNode<T> p)

    • getHeight

      public int getHeight()

    • getHeight

      private int getHeight(TreeNode<T> p)

    • DSW

      public void DSW()

    • createBackbone

      private void createBackbone()
      Time complexity: O(n)

    • rotateRight

      private TreeNode<T> rotateRight(TreeNode<T> grandParent, TreeNode<T> parent, TreeNode<T> leftChild)

    • createPerfectBST

      private void createPerfectBST()
      Time complexity: O(n)

    • greatestPowerOf2LessThanN

      private int greatestPowerOf2LessThanN(int n)
      . Time complexity: log(n)
      Parameters:
      n - the inout number
      Returns:
      the greatest power of 2 less than N

    • MSB

      public int MSB(int n)
      Return the index of most significant set bit: index of least significant bit is 0. Time complexity: log(n)
      Parameters:
      n - the input number
      Returns:
      the index of most significant set bit

    • makeRotations

      private void makeRotations(int bound)

    • rotateLeft

      private void rotateLeft(TreeNode<T> grandParent, TreeNode<T> parent, TreeNode<T> rightChild)

    • mergeTrees

      public void mergeTrees(BinarySearchTree<T> that)

    • mergeTrees

      private void mergeTrees(BinarySearchTree<T> that, TreeNode<T> p)

    • asList

      public List<T> asList()

    • asList

      private void asList(List<T> l, TreeNode<T> p)